// https://leetcode.cn/problems/binary-tree-right-side-view/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 层序遍历二叉树获取右视图
// 2. 使用队列进行广度优先搜索
// 3. 记录每层最后一个节点的值
// 4. 按层处理保证右视图顺序
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <queue>
#include <vector>
#include <string>
#include <algorithm>

struct TreeNode 
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

TreeNode* buildTree(const vector<string>& nodes) 
{
    if (nodes.empty() || nodes[0] == "null") return nullptr;
    
    TreeNode* root = new TreeNode(stoi(nodes[0]));
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    
    while (!q.empty() && i < nodes.size()) 
    {
        TreeNode* current = q.front();
        q.pop();
        
        if (i < nodes.size() && nodes[i] != "null") 
        {
            current->left = new TreeNode(stoi(nodes[i]));
            q.push(current->left);
        }
        i++;
        
        if (i < nodes.size() && nodes[i] != "null") 
        {
            current->right = new TreeNode(stoi(nodes[i]));
            q.push(current->right);
        }
        i++;
    }
    
    return root;
}

class Solution 
{
public:
    vector<int> rightSideView(TreeNode* root)
    {
        if (root == nullptr) return {};

        queue<TreeNode*> q;
        q.push(root);

        vector<int> ret;
        while (q.empty() == false)
        {
            int sz = q.size();
            for (int i = 0 ; i < sz ; i++)
            {
                auto front = q.front();
                q.pop();

                if (i == sz - 1)
                {
                    ret.push_back(front->val);
                }

                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }
        }

        return ret;
    }
};

int main()
{
    vector<string> nodes1 = {"1","2","3","null","5","null","4"};
    vector<string> nodes2 = {"1","2","3","4","null","null","null","5"};

    auto root1 = buildTree(nodes1);
    auto root2 = buildTree(nodes2);

    Solution sol;

    auto v1 = sol.rightSideView(root1);
    auto v2 = sol.rightSideView(root2);

    for (const int& num : v1)
        cout << num << " ";
    cout << endl;

    for (const int& num : v2)
        cout << num << " ";
    cout << endl;

    return 0;
}